1. Field of the Invention
This invention relates to systems for protection of information, and more specifically to information storage systems in which information is fragmented and retrieval of information can be controlled by trusted third parties.
2. Description of Prior Art
In "Principles of Database and Knowledge-Base Systems, volume II" (Computer Science Press, 1989, ISBN 0-7167-10069-X) by Jeffrey D. Ullman it is described how databases may be fragmented, either vertically or horizontally. However, fragmentation is described only in the context of distributed databases, for increasing efficiency and lowering cost. Vertical fragmentation corresponds to dividing a table into not necessarily disjoint subsets of columns (i.e. breaking up the rows). Horizontal fragmentation corresponds to dividing a table into not necessarily disjoint subsets of rows (i.e. breaking up the columns). Also, a technique is known, in the prior art, for introducing a unique identifier for each record, inserted to enable handling of updates of these records in distributed databases. The above ideas have been expressed in various places throughout the literature.
In "Cryptography and Data Security" (Addison-Wesley, 1982, ISBN 0-301-10150-5) by Dorothy Denning it is described how sensitive information (in general, information that is not meant to be public) that is stored in a database can be protected by a strict policy to restrict retrieval to certain allowed queries. Although many such techniques have been proposed, they are limited in the sense that, when evaluating whether or not to allow a certain query, it is often impossible to take into consideration all previously allowed queries, because a complete and reliable query history can not be established. Moreover, all these proposals lack countermeasures against abuse of the database by an insider.
Forced centralized retrieval, as offered by the present invention, potentially increases the control over allowed queries.
In "Untraceable Electronic Mail, Return Addresses, and Digital Pseudonyms" (Communications of the ACM, February 1981, Volume 24, Number 2) by David Chaum, one of the present applicants, the notion of a so-called mix is introduced to achieve electronic mail systems in which the sender remains unknown to the receiver. Messages are sent via the mix-operated by a trusted third party. Encryption by the sender of the message with the public key of the designated receiver, and of the designated receiver's address with the public key of the trusted third party, ensures that only the intended receiver can read the content of the message, and that the message can only reach the receiver via the trusted third party. When forwarding the message, this party does not reveal the identity of the sender to the receiver. Instead of a single mix, a series, of any number, of mixes can be used as well.
Forcing messages to be routed via trusted third parties, by applying the mix mechanism, is fundamental to achieving the property of controlled information retrieval achieved by the present invention.
Steven H. Low, Nicolas F. Maxemchuk, et al. from AT&T Bell Labs wrote several papers on privacy protection for credit card systems ("Anonymous Credit Cards", Proceedings of the 2.sup.nd ACM Conference on Computer and Communications Security, November 2-4, 1994), a health insurance architecture, and other systems--all introducing similar architectures and methods. Central to their approach is the use of so-called double-locked boxes--an application of the mix mechanism as introduced by Chaum--and the introduction of pseudonyms for individuals. In their systems, information-storing parties identify individuals under a pseudonym. The correspondence between the real-life identity and a set of pseudonyms relating to an individual is only known to this individual. As a result of this, individuals have to take an active part in the system during most operations. However, in many applications it is not needed, not wanted, or simply impossible to require individuals to take part in each data retrieval procedure involving information regarding these individuals. Furthermore, in practice, the storage of the pseudonyms by the individual, and the construction of double-locked boxes by the individual, requires that individuals carry a device suitable for performing this function.
In the present invention, individuals may delegate control over retrieval of information to one or more trusted third parties. When control is delegated to multiple trusted third parties, all parties have to consent, and indeed cooperate, before access is granted. Individuals are not required to carry a device.
All current databases, and the techniques described in the above-mentioned publications, suffer from two additional major drawbacks. First, information can easily be abused when it is stored centrally or distributed but insufficiently de-fragmented, or when it can be retrieved otherwise without restrictions. Privacy legislation is both a reaction to, and an impediment to such systems. This is increasingly generating a demand for databases that cannot be abused in this way, but which can still provide the same functionality. A second drawback is that access policies required by the parties that supply the information, rely on agreements, legislation and trust; a situation that also conflicts with changing privacy legislation and increasing popular demand for reduction in the potential for abuse of provided information. The present, innovative system overcomes these drawbacks by means of methods and apparatuses for secure data-storage that allow the introduction of trusted third parties who can directly enforce access policies, and still provide all desired functionality in an efficient way.